package com.xzz.bfs;

import java.util.*;

/**
 * @author: hhz
 * @create: 2022-01-24 10:19
 * 2045. 到达目的地的第二短时间
 **/
public class SecondMinimum {
    public static void main(String[] args) {
        System.out.println(secondMinimum(5,new int[][]{{1,2},{1,3},{1,4},{3,4},{4,5}},3,5));
        System.out.println(secondMinimum(2,new int[][]{{1,2}},3,2));
    }
    public static int secondMinimum(int n, int[][] edges, int time, int change) {
        // 处理无向图路径
        //得到每个节点能指向的节点
        List<Integer>[] grap = new List[n+1];
        for (int i = 0; i <= n; i++) {
            grap[i] = new ArrayList<>();
        }
        for (int[] edge : edges) {
            grap[edge[0]].add(edge[1]);
            grap[edge[1]].add(edge[0]);
        }
        // dist1[i]记录到节点i的最短路径,就是边数
        // dist2[i]记录到节点i的次最短路径,就是边数
        int [] dist1 = new int[n+1];
        int [] dist2 = new int[n+1];
        Arrays.fill(dist1, Integer.MAX_VALUE);
        Arrays.fill(dist2, Integer.MAX_VALUE);
        //<index,step> 保存到index节点需要的步数(边数)
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{1,0});
        while (dist2[n]==Integer.MAX_VALUE){
            int[] poll = queue.poll();
            int cur = poll[0];
            int len = poll[1];
            for (Integer next : grap[cur]) {
                if(len+1<dist1[next]){
                    dist1[next] = len+1;
                    queue.offer(new int[]{next,len+1});
                }else if(len+1>dist1[next] && len+1<dist2[next]){
                    dist2[next]=len+1;
                    queue.offer(new int[]{next,len+1});
                }
            }
        }
        int result = 0;
        for (int i = 0; i < dist2[n]; i++) {
            int num = result % (2 * change);
            // 需要加入等红绿灯的时间 由于红绿转换 所以循环是时间 2*change
            if (num >= change) { //遇到红灯
                // 比如time等于3 change=5 这个时候result如果等于6 就需要等4分钟 （2*5）-6%10 = 10-6 = 4
                result = result + (2 * change - num);
            }
            // 加上路径的时间
            result = result + time;
        }

        return result;
    }
}
